package com.aug_leo.datastructure.stack;

import java.util.LinkedList;

/**
 * 中缀表达式转后缀
 */
public class E03InfixToSuffix {

    public static void test() {
        int a = 1;
        int b = 2;
        int c = 5;
        int d = a + b * c; // 中缀 abc*+
    }

    /*
        思路:

        /   /
        /   /
        /   /
       --------

       a+b              ab+
       a+b-c            ab+c-
       a*b+c            ab*c+
       a+b*c            abc*+
       a+b*c-d          abc*+d-
       (a+b)*c          ab+c*
       (a+b*c-d)*e      abc*+d-e*
       a*(b+c)          abc+*

        1. 遇到非运算符 直接拼串
        2. 遇到 + - * /
            - 它的优先级比栈顶运算符高, 入栈, 如: 栈中是 + 当前是 *
            - 否则把栈里优先级 >= 它 的都出栈, 它再入栈, 如: 栈中是 +*, 当前是 -
        3. 遍历完成, 栈里剩余运算符依次出栈
        4. 带()
            - 左括号直接入栈, 左括号优先设置为0
            - 右括号就把栈里到左括号为止的所有运算符出栈
     */
    public static void main(String[] args) {
        System.out.println(infixToSuffix("a+b"));
        System.out.println(infixToSuffix("a+b-c"));
        System.out.println(infixToSuffix("a+b*c"));
        System.out.println(infixToSuffix("a*b-c"));
        System.out.println(infixToSuffix("(a+b)*c"));
        System.out.println(infixToSuffix("(a+b*c-d)*e"));
        System.out.println(infixToSuffix("a*(b+c)"));
    }

    /**
     * 获取运算符的优先级
     *
     * @param c 运算符字符
     * @return 运算符的优先级，*和/为2，+和-为1
     * @throws IllegalArgumentException 如果传入的字符不是合法的运算符
     */
    static int priority(char c) {
        return switch (c) {
            case '*', '/' -> 2;
            case '+', '-' -> 1;
            case '(' -> 0;
            default -> throw new IllegalArgumentException("不合法的运算符: " + c);
        };
    }

    /**
     * 将中缀表达式转换为后缀表达式
     *
     * @param exp 中缀表达式字符串
     * @return 转换后的后缀表达式字符串
     */
    static String infixToSuffix(String exp) {
        // 创建一个栈用于存放运算符
        LinkedList<Character> stack = new LinkedList<>();
        // 创建一个StringBuilder用于构建后缀表达式
        StringBuilder sb = new StringBuilder(exp.length());
        // 遍历中缀表达式字符
        for (int i = 0; i < exp.length(); i++) {
            char c = exp.charAt(i);
            // 根据字符类型处理
            switch (c) {
                case '+', '-', '*', '/' -> {
                    // 如果栈为空，则直接入栈
                    if (stack.isEmpty()) {
                        stack.push(c);
                    } else {
                        // 如果当前运算符优先级大于栈顶运算符，则入栈
                        if (priority(c) > priority(stack.peek())) {
                            stack.push(c);
                        } else {
                            // 如果当前运算符优先级小于等于栈顶运算符，则将栈中的运算符弹出并加入结果，直到栈为空或栈顶运算符优先级小于当前运算符
                            while (!stack.isEmpty() && priority(stack.peek()) >= priority(c)) {
                                sb.append(stack.pop());
                            }
                            stack.push(c);
                        }
                    }
                }

                case '(' -> {
                    // 左括号直接入栈
                    stack.push(c);
                }
                case ')' -> {
                    // 右括号弹出栈中运算符并加入结果，直到遇到左括号为止
                    while (!stack.isEmpty() && stack.peek() != '(') {
                        sb.append(stack.pop());
                    }
                    // 最后左括号出栈
                    stack.pop();
                }
                default -> {
                    // 默认情况下，字符为操作数，直接加入结果
                    sb.append(c);
                }
            }
        }

        // 将栈中剩余的运算符弹出并加入结果
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        // 返回后缀表达式字符串
        return sb.toString();
    }
}
